# Python 2.6.4
# Project Euler, Problem 70all
# Copyright 2010 Talha Zaman

def factors(limit):
    sieve = [[] for i in range(0, limit)]
    sieve[0] = sieve[1] = [1]
    for i in range(2,limit):
        if len(sieve[i]): continue
        for j in range(2*i, limit, i):
            sieve[j].append(i)
    return sieve

def sphi(limit):
    sieve = [i for i in range(limit)]
    sieve[0] = sieve[1] = 1
    for i in range(2,limit):
        if sieve[i]<i: continue
        for j in range(2*i, limit, i):
            sieve[j] = sieve[j]*(i-1)/i
        sieve[i] = i-1
    return sieve

def phi(n, fac):
    if len(fac[n])==0: return n-1
    for f in fac[n]: n = n*(f-1) / f
    return n

def isprime(n):
    from math import sqrt
    if n<=1: return False
    if n%2==0 and n!=2: return False
    if n%3==0 and n!=3: return False
    sn = int(sqrt(n))+2
    for i in range(5,sn,6):
        if n%i==0: return False
        if n%(i+2)==0: return False
    return True

def getphi(n, primes):
    if n<=1: return 1
    if n in primes: return n-1
    ph = n
    for p in primes:
        if p*p > n: break
        if n%p==0:
            ph = ph*(p-1)/p
            while (n%p==0): n = n/p
            if n==1: break
            if isprime(n):
                ph = ph*(n-1)/n
                break
    return ph

def isperm(n, m):
    digits = [0]*10
    for d in str(n): digits[int(d)] += 1
    for d in str(m): digits[int(d)] -= 1
    return not any(digits)



from time import clock
start = clock()
lim = 10000000
minpn = 2
num = 0
s = sphi(lim)
middle = clock()
print "Sieve:", middle-start
for i in range(2, lim):
    if not isperm(i, s[i]): continue
    npn = i / float(s[i])
    if npn<minpn:
        minpn = npn
        num = i
stop = clock()
print num
print "Search:", stop-middle
print "Total:", stop-start
